package cn.edu.zufe.mjt.recursion;

import java.util.Scanner;

/**
 * 递归问题 —— 路径统计 ①
 * 路径统计，给你一个 n*n 的数组，要求从 [0,0] 到 [n-1,n-1] 的路径数，每次可以选择往下走或者往右走一步
 * 为什么可以用递归解决？
 *      假设当前位置为(x，y)，如果向右走一步，此时要解决(x，y + 1)到终点的路径数
 *      再比如，选择向下走一步，此时要解决(x+1，y)到终点的路径数
 *      依此类推…直到逐步缩小规模
 * 从递归树的角度看：
 * 本质上就是求递归树的叶子节点个数
 */
public class PathOne {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(countPath(0, 0, n));

    }

    public static int countPath(int x, int y, int n) {
        if (x == n - 1 && y == n - 1) {
            return 1;
        }
        int count = 0;
        if (x < n - 1) {
            count += countPath(x + 1, y, n);
        }
        if (y < n - 1) {
            count += countPath(x, y + 1, n);
        }
        return count;
    }
}
